/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
 * You can obtain one at http://mozilla.org/MPL/2.0/. */


var EXPORTED_SYMBOLS =
[
    "Heap"
];


/*
 * Heap algorithm is taken from:
 * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
 */

function Heap(compare)
{
    this.heap = [];
    this.compare = (compare ? compare : this._compare);
}

Heap.prototype =
{
    get length() { return this.heap.length; },
    
    push: function Heap_push(value)
    {
        var heap = this.heap;
        var compare = this.compare;
        var index = heap.length + 1;
        var parent = index >> 1;
        
        while ((parent > 0) && (compare(value, heap[parent - 1]) > 0))
        {
            heap[index - 1] = heap[parent - 1];
            index = parent;
            parent = parent >> 1;
        }
        
        heap[index - 1] = value;
    },
    
    peek: function Heap_peek()
    {
        var heap = this.heap;
        var length = heap.length;
        
        if (length == 0)
            throw new Error("heap is empty");
        
        return heap[0];
    },
    
    pop: function Heap_pop()
    {
        var heap = this.heap;
        var length = heap.length;
        
        if (length == 0)
            throw new Error("heap is empty");
        
        var value = heap[0];
        heap[0] = heap[length - 1];
        heap.length = length - 1;
        this._heapify(1);
        
        return value;
    },
    
    _heapify: function Heap__heapify(index)
    {
        var heap = this.heap;
        var compare = this.compare;
        var length = heap.length;
        var left = index * 2;
        var right = index * 2 + 1;
        var max = index;
        
        if ((left <= length) && (compare(heap[left - 1], heap[max - 1]) > 0))
            max = left;
        if ((right <= length) && (compare(heap[right - 1], heap[max - 1]) > 0))
            max = right;
        
        if (max != index)
        {
            [heap[index - 1], heap[max - 1]] = [heap[max - 1], heap[index - 1]];
            this._heapify(max);
        }
    },
    
    _compare: function Heap__compare(a, b)
    {
        return ((a < b) ? -1 : ((a == b) ? 0 : 1));
    }
}
